\documentclass[12pt]{beamer}

\usepackage{fontspec} %支持文章中字体配置
\usepackage{amsmath} %支持更多数学格式
\usepackage{xcolor,graphicx}


\setsansfont{WenQuanYi Zen Hei}

% \mode<beamer>{%
%   \usetheme[hideothersubsections,
%   right,width=22mm]{Goettingen}
% }

\title{压缩感知及其恢复算法}
\subtitle{Compressive Sensing}
\author[]{曹金}

\institute{UESTC}
%\titlegraphic{\includegraphics[width=20mm]{USTL}}

\date{2012}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{主要内容}
  \tableofcontents
\end{frame}

\section{压缩感知理论}

\begin{frame}
  \frametitle{数学模型}
  \[
  y = A x
  \]
  \begin{block}{}
    原向量$x \in R^n$ , 观测矩阵$A \in R^{m \times n}$, 观测向量$y \in R^m$\\
    \begin{itemize}
    \item sensing matrix, 观测矩阵
    \end{itemize}
    实际意义: \\通过已知的矩阵A和得到的向量y, 恢复出来原向量x.
    
  \end{block}
  通过解下面的方程
  \[
  A \hat{x} = y
  \]

\end{frame}

\begin{frame}
  \frametitle{线性方程组的解和秩的关系}

  \begin{block}{有解的情况}
      \[
       A \hat{x} = y
      \]
      \begin{itemize}
      \item rank(A) < n, 有无穷多解
      \item rand(A) = n, 有唯一解
      \end{itemize}
    \end{block}

\end{frame}
  

\begin{frame}
  \frametitle{CS的情况}
  \[
  \left[
    \begin{array}{c}
      \\
      \\
     y \\
      \\
      \\
    \end{array}
    \right] = 
    \left[
      \begin{array}{ccccccccccc}
        & & & & & & & & & &\\
        & & & & & & & & & & \\
        & & & & & A & & & & &\\
        & & & & & & & & & & \\
        & & & & & & & & & &\\
      \end{array}
      \right] \cdot
      \left[
        \begin{array}{c}
          \\
          \\
          \\
          \\
          x \\
          \\
          \\
          \\
          \\
        \end{array}
        \right]
        \]
        \begin{block}{}
          此时, 解方程$A\hat{x} = y$将得到无数解, 这样无法准确恢复出原向量$\hat{x} = x$.\\
          但是如果已知x为稀疏向量(信号)的话, 满足一定条件的话, 可以得到唯一解x
        \end{block}
        
\end{frame}

\begin{frame}
  \frametitle{稀疏信号}
  x是s-sparse的, 表示向量x的所有分量中仅有s个非零值, 其他都为零.\\
  \begin{block}{例如}
    $x = (0, 1, 2, 3, 4, 0, 0, 0, 0)^T $是一个4-sparse的向量.
  \end{block}
  \begin{block}{一般意义下的稀疏信号}
    给出一个信号f(t), 通常在时间域上不是稀疏的, 但是变到频域上后, 就是稀疏的了.\\
    稀疏信号是在某个变换域上(某组基)的稀疏信号.\\
    例如, $f = \Psi x$, x是s-sparse的一个向量.
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{稀疏信号的准确恢复}
  \begin{block}{}
    如果我们已知f在基$\Psi$下是s-sparse的, 观测矩阵$\Phi$相关度很小, 通过解下面的优化问题可以以很高的概率得到原信号x
    \[
    \min_{\hat{x} \in R^n} \| \hat{x} \|_{\ell_1} \quad \text{subject to} \quad \Phi f = \Phi \Psi x = y
    \]
  \end{block}
  
  \begin{itemize}
  \item 若$m \cdot C_M \cdot (\log n)^{-1} \ge s$, 则$P(\hat{x} = x) \ge 1 - O(n^{-M})$
  \item 若$m \ge c \cdot \mu^2 (\Phi, \Psi) \cdot s \cdot \log(n/\delta)$, 则$P(\hat{x} = x) \ge 1 - \delta$
  \end{itemize}
  注: 将问题重新写为$y = \Phi f = \Phi \Psi x = A x$
\end{frame}

\begin{frame}
  \frametitle{RIP}
  \framesubtitle{restricted isometry propety}
  \begin{block}{定义}
    x是s-sparse的, 对于观测矩阵A定义$\delta_S$(restricted isometry constants)为一个很小的数, 满足下面的不等式:
    \[
    (1 - \delta_S) \| x \|_{\ell_2}^2 \le \| A x \|_{\ell_2}^2 \le (1 + \delta_S) \| x \|_{\ell_2}^2
    \]
  \end{block}
  取A的任意S列,这S列个向量组成的矩阵有多像一个正交矩阵.
  \begin{itemize}
  \item $\delta_S$是矩阵A的一个特征.
  \item $\delta_S \ge 0$
  \item $\delta_S$越小, A的任意S列越像正交矩阵
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{block}{关于正交矩阵}
    正交矩阵具有一个性质:\\
    如果A为正交矩阵, 则有$\| A x \|_{\ell_2} = \| x \|_{\ell_2}$
  \end{block}
  \begin{block}{将$\delta_S$定义式变形}
    \[
    (1 - \delta_S) \le \frac{\| A x \|_{\ell_2}}{\| x \|_{\ell_2}} \le (1 + \delta_S)
    \]
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{确定性的结论}
  \begin{block}{结论1}
    如果$\delta_{2S} < 1$, 则
    \[
    \min_{\hat{x} \in R^n} \| \hat{x} \|_{\ell_0} \quad \text{subject to} \quad A \hat{x} = y
    \]
    有唯一解, $\hat{x} = x$
  \end{block}
  \begin{block}{结论2}
    如果$\delta_{2S} < \sqrt{2} - 1$, 则
    \[
    \min_{\hat{x} \in R^n} \| \hat{x} \|_{\ell_1} \quad \text{subject to} \quad A \hat{x} = y
    \]
    有唯一解, $\hat{x} = x$
  \end{block}

\end{frame}

\begin{frame}
  \frametitle{随机矩阵}
  寻找一些观测矩阵, 它们的$\delta_S$满足RIP.\\
  随机矩阵以很高的概率满足RIP, 如: 
  \[
  A = (a_{ij})_{m \times n}, \quad a_{ij} \sim N(0, 1/m)
  \]
\end{frame}

\begin{frame}
  \frametitle{CS示意图}
  \begin{figure}
    \centering
    \includegraphics[width=1.0\textwidth]{Screenshot.png}
    \caption{CS}
  \end{figure}
\end{frame}


\section{恢复算法}

\begin{frame}
  \frametitle{常见算法}
  \begin{enumerate}
  \item 最优化的方法: $\ell_1$范数最小化
  \item 贪婪算法: matching pursuit
  \end{enumerate}
  贪婪算法不是最准确的, 但是计算量小. 在某些场合可以做为替代的方法来恢复信号.
\end{frame}

\begin{frame}
  \frametitle{贪婪算法}
  试图在每一步采用当前状态下最好或最有利的选择
  \begin{block}{例子}
    已知钱币的面值仅有10元, 5元和1元三种. 试用最少的钱币数量来表示37元. \pause
    \[
    37 = 3 \times 10 + 7 \pause
    7 = 1 \times 5 + 2 \pause
    2 = 2 \times 1 \pause
    钱币总个数 = 3 + 1 + 2 = 6
    \]
    对于每一次剩余的价格, 总选取面值最大的钱币.
  \end{block}
  在有些情况下, 贪婪算法不能得到最优的解.
\end{frame}

\begin{frame}
  \frametitle{Matching Pursuit}  
  在1993年, 由Mallat, S. G.和Z. Zhang提出.
  \begin{block}{算法}
    在$L^2(R)$中定义(找)一组基, 或者称作是Dictionary, $D = \{g_n(t) | n = 0, 1, \dots, N \}$.
    现在将f(t)用这组基展开, 是展开后的项数最少. 
    \[
    f(t) = \sum_{n = 0}^M \langle f(t), g_n(t) \rangle g_n(t) + Rf
    \]
  \end{block}
\end{frame}


\begin{frame}
  \frametitle{Matching Pursuit}
  \begin{block}{步骤}
    \begin{enumerate}
    \item n = 0
    \item 计算所有$\langle f(t), g_n(t) \rangle, n = 0, 1, \dots, N$
    \item 找到使内积值最大的那个$g_k(t), k \in [0, N]$
    \item $f(t) = \sum_{n = 0}^M \langle f(t), g_n(t) \rangle g_n(t) + Rf_n$
    \item n = n + 1, 回到第2步, 将$Rf_n$按同样的方法投影到其他的基上.
    \item 满足停止条件就停止, 如 $\| Rf_n \| < threshold$
    \end{enumerate}
  \end{block}
\end{frame}


\begin{frame}
  问题讨论
\end{frame}

\end{document}
